0554. 砖墙【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 哈希表

1. 📝 题目描述

• leetcode

你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和相等。

你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。

给你一个二维数组 wall，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少，并且返回 穿过的砖块数量。

---

示例 1：

输入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
输出：2

示例 2：

输入：wall = [[1],[1],[1]]
输出：3

---

提示：

• n == wall.length
• 1 <= n <= 10^4
• 1 <= wall[i].length <= 10^4
• 1 <= sum(wall[i].length) <= 2 * 10^4
• 对于每一行 i，sum(wall[i]) 是相同的
• 1 <= wall[i][j] <= 2^31 - 1

2. 🎯 s.1 - 哈希表

c

#define MAX_SIZE 20001
typedef struct { int key; int val; } Entry;
Entry hashMap[MAX_SIZE];
int used[MAX_SIZE];

int hash(int key) {
    int h = key % MAX_SIZE;
    return h < 0 ? h + MAX_SIZE : h;
}

void put(int key) {
    int h = hash(key);
    while (used[h]) {
        if (hashMap[h].key == key) { hashMap[h].val++; return; }
        h = (h + 1) % MAX_SIZE;
    }
    used[h] = 1;
    hashMap[h].key = key;
    hashMap[h].val = 1;
}

int leastBricks(int** wall, int wallSize, int* wallColSize) {
    memset(used, 0, sizeof(used));
    int maxGap = 0;
    for (int i = 0; i < wallSize; i++) {
        int sum = 0;
        for (int j = 0; j < wallColSize[i] - 1; j++) {
            sum += wall[i][j];
            put(sum);
        }
    }
    for (int i = 0; i < MAX_SIZE; i++) {
        if (used[i] && hashMap[i].val > maxGap) maxGap = hashMap[i].val;
    }
    return wallSize - maxGap;
}

js

/**
 * @param {number[][]} wall
 * @return {number}
 */
var leastBricks = function (wall) {
  const map = new Map()
  for (const row of wall) {
    let sum = 0
    for (let i = 0; i < row.length - 1; i++) {
      sum += row[i]
      map.set(sum, (map.get(sum) || 0) + 1)
    }
  }
  let maxGap = 0
  for (const v of map.values()) {
    maxGap = Math.max(maxGap, v)
  }
  return wall.length - maxGap
}

py

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        cnt = defaultdict(int)
        for row in wall:
            s = 0
            for i in range(len(row) - 1):
                s += row[i]
                cnt[s] += 1
        return len(wall) - max(cnt.values(), default=0)

• 时间复杂度：$O(nm)$，其中 n 是行数，m 是每行平均砖块数
• 空间复杂度：$O(nm)$

算法思路：

• 统计每行的缝隙位置（前缀和），记录每个位置出现的次数
• 出现次数最多的缝隙位置对应穿过砖块数最少，穿过数 = 行数 - 最大缝隙数